//给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 
//
// 进阶：不要 使用任何内置的库函数，如 sqrt 。 
//
// 
//
// 示例 1： 
//
// 
//输入：num = 16
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：num = 14
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= num <= 2^31 - 1 
// 
// Related Topics 数学 二分查找 
// 👍 326 👎 0

package leetcode.editor.cn;
public class P367ValidPerfectSquare {
    public static void main(String[] args) {
        Solution solution = new P367ValidPerfectSquare().new Solution();
        System.out.println(solution.isPerfectSquare(16));
        System.out.println(solution.isPerfectSquare(15));
        System.out.println(solution.isPerfectSquare(5));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isPerfectSquare2(int num) {
        int left = 1, right = num;
        int middle, temp;
        while (left <= right) {
            middle = left + ((right - left) >> 1);
            temp = num / middle;  // 二分查找，用x/m<m而不是m*m>x防止溢出
            if (temp == middle && (num-1)/ middle != temp) {
                return true;
            } else  if (temp < middle) {
                right = middle -1;
            } else {
                left = middle + 1;
            }
        }
        return false;
    }

    // 优化
    public boolean isPerfectSquare(int num) {
        int left = 1, right = num;
        int middle, temp;
        while (left <= right) {
            middle = left + ((right - left) >> 1);
            temp = num / middle;  // 二分查找，用x/m<m而不是m*m>x防止溢出
            if (temp == middle && (num) % middle == 0) {  // 这里用取余
                return true;
            } else  if (temp < middle) {
                right = middle -1;
            } else {
                left = middle + 1;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}